home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1998 July / EnigmA AMIGA RUN 29 (1998)(G.R. Edizioni)(IT)[!][issue 1998-07 & 08].iso / earcd / phase5 / lha-ppc / src / dhuf.c < prev    next >
C/C++ Source or Header  |  1997-12-04  |  5KB  |  301 lines
  1. /**************************************************************
  2.     title   dhuf.c
  3. ***************************************************************
  4.     Dynamic Huffman routine
  5.                                                 H.Yoshizaki
  6. **************************************************************/
  7. #include <stdio.h>
  8. #include "slidehuf.h"
  9.  
  10. #define N_CHAR      (256 + 60 - THRESHOLD + 1)
  11. #define TREESIZE_C  (N_CHAR * 2)
  12. #define TREESIZE_P  (128 * 2)
  13. #define TREESIZE    (TREESIZE_C + TREESIZE_P)
  14. #define ROOT_C      0
  15. #define ROOT_P      TREESIZE_C
  16.  
  17. unsigned int n_max;
  18.  
  19. static short child [TREESIZE],
  20.              parent[TREESIZE],
  21.              block [TREESIZE],
  22.              edge  [TREESIZE],
  23.              stock [TREESIZE],
  24.              node  [TREESIZE / 2];
  25.  
  26. static unsigned short freq[TREESIZE];
  27.  
  28. static unsigned short total_p;
  29. static int avail, n1;
  30. static int most_p, nn;
  31. static unsigned long nextcount;
  32.  
  33. void start_c_dyn(void)
  34. {
  35.     int i, j, f;
  36.  
  37.     n1 = (n_max >= 256 + maxmatch - THRESHOLD + 1) ? 512 : n_max - 1;
  38.     for (i = 0; i < TREESIZE_C; i++) {
  39.         stock[i] = i;
  40.         block[i] = 0;
  41.     }
  42.     for (i = 0, j = n_max * 2 - 2; i < n_max; i++, j--) {
  43.         freq[j] = 1;
  44.         child[j] = ~i;
  45.         node[i] = j;
  46.         block[j] = 1;
  47.     }
  48.     avail = 2;
  49.     edge[1] = n_max - 1;
  50.     i = n_max * 2 - 2;
  51.     while (j >= 0) {
  52.         f = freq[j] = freq[i] + freq[i - 1];
  53.         child[j] = i;
  54.         parent[i] = parent[i - 1] = j;
  55.         if (f == freq[j + 1]) {
  56.             edge[block[j] = block[j + 1]] = j;
  57.         } else {
  58.             edge[block[j] = stock[avail++]] = j;
  59.         }
  60.         i -= 2;
  61.         j--;
  62.     }
  63. }
  64.  
  65. static void start_p_dyn(void)
  66. {
  67.     freq[ROOT_P] = 1;
  68.     child[ROOT_P] = ~(N_CHAR);
  69.     node[N_CHAR] = ROOT_P;
  70.     edge[block[ROOT_P] = stock[avail++]] = ROOT_P;
  71.     most_p = ROOT_P;
  72.     total_p = 0;
  73.     nn = 1 << dicbit;
  74.     nextcount = 64;
  75. }
  76.  
  77. void decode_start_dyn(void)
  78. {
  79.     n_max = 286;
  80.     maxmatch = MAXMATCH;
  81.     init_getbits();
  82.     start_c_dyn();
  83.     start_p_dyn();
  84. }
  85.  
  86. static void reconst(int start, int end)
  87. {
  88.     int i, j, k, l, b = 0;
  89.     unsigned int f, g;
  90.  
  91.     for (i = j = start; i < end; i++) {
  92.         if ((k = child[i]) < 0) {
  93.             freq[j] = (freq[i] + 1) / 2;
  94.             child[j] = k;
  95.             j++;
  96.         }
  97.         if (edge[b = block[i]] == i) {
  98.             stock[--avail] = b;
  99.         }
  100.     }
  101.     j--;
  102.     i = end - 1;
  103.     l = end - 2;
  104.     while (i >= start) {
  105.         while (i >= l) {
  106.             freq[i] = freq[j]; child[i] = child[j];
  107.             i--, j--;
  108.         }
  109.         f = freq[l] + freq[l + 1];
  110.         for (k = start; f < freq[k]; k++);
  111.         while(j >= k) {
  112.             freq[i] = freq[j]; child[i] = child[j];
  113.             i--, j--;
  114.         }
  115.         freq[i] = f; child[i] = l + 1;
  116.         i--;
  117.         l -= 2;
  118.     }
  119.     f = 0;
  120.     for (i = start; i < end; i++) {
  121.         if ((j = child[i]) < 0) node[~j] = i;
  122.         else parent[j] = parent[j - 1] = i;
  123.         if ((g = freq[i]) == f) {
  124.             block[i] = b;
  125.         } else {
  126.             edge[b = block[i] = stock[avail++]] = i;
  127.             f = g;
  128.         }
  129.     }
  130. }
  131.  
  132. static int swap_inc(int p)
  133. {
  134.     int b, q, r, s;
  135.  
  136.     b = block[p];
  137.     if ((q = edge[b]) != p) {    /* swap for leader */
  138.         r = child[p]; s = child[q];
  139.         child[p] = s; child[q] = r;
  140.         if (r >= 0) parent[r] = parent[r - 1] = q;
  141.         else        node[~r] = q;
  142.         if (s >= 0)    parent[s] = parent[s - 1] = p;
  143.         else        node[~s] = p;
  144.         p = q;
  145.         goto Adjust;
  146.     } else if (b == block[p + 1]) {
  147. Adjust:
  148.         edge[b]++;
  149.         if (++freq[p] == freq[p - 1]) {
  150.             block[p] = block[p - 1];
  151.         } else {
  152.             edge[block[p] = stock[avail++]] = p;    /* create block */
  153.         }
  154.     } else if (++freq[p] == freq[p - 1]) {
  155.         stock[--avail] = b;        /* delete block */
  156.         block[p] = block[p - 1];
  157.     }
  158.     return parent[p];
  159. }
  160.  
  161. static void update_c(int p)
  162. {
  163.     int q;
  164.  
  165.     if (freq[ROOT_C] == 0x8000) {
  166.         reconst(0, n_max * 2 - 1);
  167.     }
  168.     freq[ROOT_C]++;
  169.     q = node[p];
  170.     do {
  171.         q = swap_inc(q);
  172.     } while (q != ROOT_C);
  173. }
  174.  
  175. static void update_p(int p)
  176. {
  177.     int q;
  178.  
  179.     if (total_p == 0x8000) {
  180.         reconst(ROOT_P, most_p + 1);
  181.         total_p = freq[ROOT_P];
  182.         freq[ROOT_P] = 0xffff;
  183.     }
  184.     q = node[p + N_CHAR];
  185.     while (q != ROOT_P) {
  186.         q = swap_inc(q);
  187.     }
  188.     total_p++;
  189. }
  190.  
  191. static void make_new_node(int p)
  192. {
  193.     int q, r;
  194.  
  195.     r = most_p + 1; q = r + 1;
  196.     node[~(child[r] = child[most_p])] = r;
  197.     child[q] = ~(p + N_CHAR);
  198.     child[most_p] = q;
  199.     freq[r] = freq[most_p];
  200.     freq[q] = 0;
  201.     block[r] = block[most_p];
  202.     if (most_p == ROOT_P) {
  203.         freq[ROOT_P] = 0xffff;
  204.         edge[block[ROOT_P]]++;
  205.     }
  206.     parent[r] = parent[q] = most_p;
  207.     edge[block[q] = stock[avail++]] = node[p + N_CHAR] = most_p = q;
  208.     update_p(p);
  209. }
  210.  
  211. static void encode_c_dyn(int c)
  212. {
  213.     unsigned int bits;
  214.     int p, d, cnt;
  215.  
  216.     d = c - n1;
  217.     if (d >= 0) {
  218.         c = n1;
  219.     }
  220.     cnt = bits = 0;  
  221.     p = node[c];
  222.     do {
  223.         bits >>= 1;
  224.         if (p & 1) {
  225.             bits |= 0x8000;
  226.         }
  227.         if (++cnt == 16) {
  228.             putcode(16, bits);
  229.             cnt = bits = 0;
  230.         }
  231.     } while ((p = parent[p]) != ROOT_C);
  232.     putcode(cnt, bits);
  233.     if (d >= 0) putbits(8, d);
  234.     update_c(c);
  235. }
  236.  
  237. unsigned short decode_c_dyn(void)
  238. {
  239.     unsigned short c;
  240.     short buf, cnt;
  241.  
  242.     c = child[ROOT_C];
  243.     buf = bitbuf;
  244.     cnt = 0;
  245.     do {
  246.         c = child[c - (buf < 0)];
  247.         buf <<= 1;
  248.         if (++cnt == 16) {
  249.             fillbuf(16);
  250.             buf = bitbuf; cnt = 0;
  251.         }
  252.     } while (c > 0);
  253.     fillbuf(cnt);
  254.     c = ~c;
  255.     update_c(c);
  256.     if (c == n1) c += getbits(8);
  257.     return c;
  258. }
  259.  
  260. unsigned short decode_p_dyn(void)
  261. {
  262.     int c;
  263.     short buf, cnt;
  264.  
  265.     while (count > nextcount) {
  266.         make_new_node(nextcount / 64);
  267.         if ((nextcount += 64) >= nn)
  268.             nextcount = 0xffffffff;
  269.     }
  270.     c = child[ROOT_P];
  271.     buf = bitbuf; cnt = 0;
  272.     while (c > 0) {
  273.         c = child[c - (buf < 0)];
  274.         buf <<= 1;
  275.         if (++cnt == 16) {
  276.             fillbuf(16);
  277.             buf = bitbuf; cnt = 0;
  278.         }
  279.     }
  280.     fillbuf(cnt);
  281.     c = (~c) - N_CHAR;
  282.     update_p(c);
  283.  
  284.     return (unsigned short)((c << 6) + getbits(6));
  285. }
  286.  
  287. void output_dyn( code , pos )
  288. int code;
  289. unsigned int pos;
  290. {
  291.     encode_c_dyn(code);
  292.     if (code >= 0x100) {
  293.         encode_p_st0(pos);
  294.     }
  295. }
  296.  
  297. void encode_end_dyn(void)
  298. {
  299.     putcode(7, 0);
  300. }
  301.